package 算法基础模板.chapter_02;

import java.util.Arrays;

/**
 * @author Summerday
 */
public class HashTemplate {

    private final int N = 16;

    private final int nul = 0x3f3f3f3f;

    int[] h = new int[N];

    int[] e = new int[N];
    int[] ne = new int[N];
    int idx;

    {
        //Arrays.fill(h, -1);
        Arrays.fill(h, nul);
    }

    public static void main (String[] args) {
        //HashTemplate template = new HashTemplate();
        //template.insert(1);
        //template.insert(2);
        //template.insert(3);
        //template.insert(4);
        //template.insert(5);
        //template.insert(17);
        //template.insert(16);
        //System.out.println(template.find(1));
        //System.out.println(template.find(3));
        //System.out.println(template.find(5));

        HashTemplate template = new HashTemplate();
        template.insert2(1);
        template.insert2(1);
        template.insert2(1);
        template.insert2(1);
        template.insert2(1);
        template.insert2(1);

        System.out.println(0x3f3f3f3f);
        System.out.println(Integer.MAX_VALUE);


    }

    // 拉链法
    void insert (int x) {
        int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx++;
    }

    boolean find (int x) {
        int k = (x % N + N) % N;
        for (int i = h[k]; i != -1; i = ne[i]) {
            if (e[i] == x) return true;
        }
        return false;
    }

    // 开放寻址法
    // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
    int find2 (int x) {
        // 开放寻址的坑位一般开 2-3 倍
        int k = (x % N + N) % N;
        // 如果这个坑有人 且 不是x 找下一个坑位
        while (h[k] != nul && h[k] != x) {
            k++;
            if (k == N) k = 0;
        }
        return k;
    }

    void insert2(int x){
        int k = find2(x);
        h[k] = x;
    }
}
